It is well recognized that the construction or manufacture of any building, machine or equipment, generally referred to as a project, requires the collective performance of a number of individual operations or tasks for successful completion. Resources are required, as example, personnel, trained to accomplish the task, capital equipment and other resources, supplies and component parts, which need to be procured or built. Each task requires a finite time, determined by past experience, for completion. And precedence must be followed, in that some tasks typically must be completed before other tasks in the project may begin.
Prudence requires planning and, particularly, formulation of a schedule that defines the “who,” “when,” “where” and “how” that is necessary for completion of the project in an orderly and efficient manner. In earlier eras, the foreman or manufacturing engineer possessed the experience, training and intellect to arrange the tasks required by the project in mind and specify which persons were to carry out the tasks, the resources and supplies required, and other necessary details. That person could also provide a reasonable estimate of the time of completion as allowed prediction of a delivery date.
As modern factory projects attained greater complexity, schedules required better definition and were more scientifically defined by persons, often now referred to as industrial engineers. With essentially pen, ink and calculator, such persons were able to search through the requirements and present the paper documents defining the tasks and the resources associated with them and to arrange the order of (sequence) tasks for completion, creating timelines of individual tasks and chronological order of the tasks commencement and completion, namely, produce a project schedule. As projects became more complex still, those scheduling techniques often proved inefficient and, while less than perfect, necessarily sufficed until the advent of automated calculating machinery, such as modern scheduling systems.
To construct a modern aircraft involves many thousands of individual tasks, a vast number of technicians and assemblers, and a large amount of resources. To prepare a schedule for such a project would likely overwhelm the genius of any person working with pen, paper and calculator and would require an inordinate amount of time for one person or even a group of people to schedule to completion with minimal errors. One should not expect that the definition of a schedule to construct an aircraft should require preparation time that exceeds the construction time of an aircraft, disregarding the realism which necessitates redefining the schedule when tasks are not completed on time as originally planned, as for example due to acts of force majeure, such as electrical failure or flood.
Further compounding the difficulty of preparing a schedule for a complex project, in the modern competitive industrial world, resources including personnel and equipment are often held to a minimum and must be allocated. Little excess personnel or equipment is available to a manufacturer. Excess resources are expensive to maintain and, if carried idle by the manufacturer for too long, results ultimately in financial collapse attributed to inefficiency. Thus, the usefulness of a schedule as an industrial tool and the benefit of efficient scheduling is well understood.
A number of scheduling systems and sequencing systems are information systems for solving complex combinatorial problems, and are often used in industry to manage the allocation of resources and personnel amongst various projects. In computational complexity theory, combinatorial optimization problems are frequently classified as “NP-hard,” and in real-world applications it is impossible to calculate a truly optimal solution to an NP-hard combinatorial problem using practical quantities of computational resources for practical periods of time.
Mathematicians and computer scientists have developed various approaches for finding good solutions (as opposed to singularly-optimal solutions) for combinatorial problems such as resource-constrained project scheduling (RCPS) and the traveling salesman problem (TSP), and such approaches may frequently be applied to more than one form of combinatorial problem. A number of differing implementations of such known solution approaches have been developed for various types of industries, types of users, types of computer hardware and the like. Consequently, the marketplace for such information systems (often termed “combinatorial solvers”) includes a range of competing options that have varying features, capabilities, and/or underlying solution approaches, and prospective purchasers face a need to evaluate at least a subset of those competing options prior to making a decision to use one of them.
The “quality” of a solution to a combinatorial problem may be measured in a number of different manners, and its quality may be related to the “cost” of formulating the respective solution. In scheduling a multitask project, for example, one measure of schedule quality may be the duration between start of the first scheduled task and completion (finish) of the last scheduled task, sometimes referred to as “span time” or “cycle time.” One example measure of schedule cost may be the time required to complete the process of formulating a schedule, that is, for the computer to execute the algorithms and process the entered task data to generate and display the schedule, often referred to as the “execution time.”
Scheduling systems, and more generally combinatorial solvers, are not created equal and vary widely in quality. Many scheduling systems either use simple methods that have low cost (e.g., low execution time), but produce schedules with inferior quality (e.g., high cycle time), or use methods that produce schedules of higher quality, but at an undesirably-high cost. These systems may, for example, produce tasks that require too much time for project completion, or require too much time to formulate the schedule.
A number of techniques for measuring the effectiveness of a combinatorial solver to solve a combinatorial problem rely on a quality metric (criterion of quality, or sometimes more simply “metric”) of its solutions (e.g., cycle time), and values of that quality metric for solutions obtained by the solver relative to the value for the optimal solution. But these techniques presuppose that the optimal solution and accordingly its quality metric are known. While this may be possible for smaller combinatorial problems, in general, the optimal solution and hence its quality metric are not possible to obtain, at least not without expending extraordinary computing resources.
It may therefore be desirable to have an apparatus and method that addresses these challenges, and improves upon existing practices.